package 面试经典150题.区间;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/6/15 15:04
 * @description https://leetcode.cn/problems/insert-interval/solutions/472553/57-cha-ru-qu-jian-mo-ni-cha-ru-xiang-jie-by-carlsu/?envType=study-plan-v2&envId=top-interview-150
 * 把插入区间分为三个阶段来处理 思路很妙
 */
public class T57插入区间 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        //先初始化索引下标
        List<int[]> result = new ArrayList<>();
        int index = 0;
        //把插入区间外面的元素放入result里面
        while (index < intervals.length && intervals[index][1] < newInterval[0]) {
            result.add(intervals[index++]);
        }
        //把新区间和其他区间合并,区间合并的时候改变index的值
        //intervals[index][0]代表该区间的左面 newIntervals[1]代表新区间的右面
        //当最左面小于等于最右面的时候就执行下面的逻辑：左左取最小值 右右取最大值
        while (index < intervals.length && intervals[index][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[index][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[index][1], newInterval[1]);
            index++;
        }
        result.add(newInterval);
        //把区间左边的其他区间加入进来
        while (index < intervals.length) {
            result.add(intervals[index++]);
        }
        //一维数组的集合调用toArray方法就会转变为二维数组，我们就只需要，在传递一下result.size即可
        return result.toArray(new int[result.size()][]);
    }
}
